package com.liunian.algorithmstudy.str.kmp;

public class StrStr28 {

    public int strStr(String haystack, String needle) {
        char[] needleCharArray = needle.toCharArray();
        int[] next = new int[needle.length()];
        getNext(needleCharArray, next);
        char[] haystackCharArray = haystack.toCharArray();
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystackCharArray[i] != needleCharArray[j]) {
                j = next[j - 1];
            }
            if (haystackCharArray[i] == needleCharArray[j]) {
                j++;
            }
            if (j == needle.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    private void getNext(char[] chars, int[] next) {
        int j = 0;
        for (int i = 1; i < chars.length; i++) {
            while (j > 0 && chars[i] != chars[j]) {
                j = next[j - 1];
            }
            if (chars[i] == chars[j]) {
                j++;
            }
            next[i] = j;
        }
    }

}
